package cn.qyd.leecode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author 邱运铎
 * 331. 验证二叉树的前序序列化
 * 示例 1:
 *
 * 输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
 * 输出: true
 * 示例 2:
 *
 * 输入: preorder = "1,#"
 * 输出: false
 * 示例 3:
 *
 * 输入: preorder = "9,#,#,1"
 * 输出: false
 * @date 2024-03-31 21:53
 */
public class TwoForkTree001 {

    public static void main(String[] args) {
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        String[] nodes = preorder.split(",");
        Stack<Integer> stack = new Stack<>();
        String root = nodes[0];
        boolean result = false;
        if ("#".equals(root)) return;
        stack.push(2);
        for (int i = 1; i < nodes.length; i++) {
            int curStackTop = stack.pop();
            if ( curStackTop - 1 > 0) {
                stack.push(curStackTop - 1);
            }
            if (!"#".equals(nodes[i])) {
                stack.push(2);
            }

            if (stack.isEmpty() && i < nodes.length - 1) {
                System.out.println(false);
                return;
            }
        }

        if (stack.isEmpty()) {
            result = true;
        }
        System.out.println(stack.isEmpty());
        System.out.println(result);
    }
}
